If a communication system which consists of many parallel channels operates asynchronously and without acknowledgement, there is neither a clock signal received by the receiver nor an acknowledgement signal sent back to the transmitter upon completion of a transmission. Each transmission consists of one or more transitions (i.e., "1" bits) which are transmitted concurrently. If the information bits from different channels do not arrive at the same time (e.g., because of a delay in one or more of the channels), the receiver may receive some "1" bits corresponding to a next transmission before the present transmission has been completed, a condition referred to as "skew".
A paper by T. Verhoeff entitled "Delay-insensitive Codes--An Overview", published in Distributed Computing, Vol. 3, pp. 1-8, 1988, suggests the use in a parallel asynchronous communication system of unordered vectors because they are "delay insensitive". However, the parallel asynchronous communication system he describes requires that an acknowledgement signal be sent by the receiver to the transmitter upon completion of each transmission and he does not disclose or suggest the use of vectors with Hamming distance properties which are unordered.
The above-identified related application [A] describes improved unordered error correcting codes and a method and apparatus for encoding and decoding said codes that satisfies distance properties between codewords of the unordered codes and thereby permits correction of a preselected number of errors.
The above-identified related application [B] discloses a method for detecting (but not correcting) skewed transitions resulting from transitions from one transmission being intermixed with transitions of another transmission.
The above-identified related application [C] discloses a method for correcting (but not detecting more than the number correctable) skewed transitions resulting from transitions from one asynchronous transmission being intermixed with transitions of another asynchronous transmission.
Neither [A], [B], nor [C] discloses a method for correcting up to one predetermined number of skewed transitions in a parallel asynchronous communication system and detecting up to a preselected greater number of skewed transitions when said one number is exceeded.
To fully understand unordered codes, it is best to consider an example. For a binary vector u of length n, u=u.sub.1,u.sub.2, . . . , u.sub.n, and the set of nonzero bits of vector u are hereafter referred to as the "support" of u. For instance, for n=6, if u=100101, the support of u is the set {1,4,6}. Two vectors u and v of length n are considered unordered when their supports are unordered as sets; i.e., neither of them contains the other. Thus, u=100101 and v=010101 are unordered because their corresponding supports are {1,4,6} and {2,4,6}. By contrast, the vector w=000101 which has a support of {4,6} would not be unordered relative to either u or v because its support {4,6} is a subset of the support of both u and v.
There is a need for a parallel asynchronous communication system which not only does not require acknowledgement between the receiver and transmitter when a transmission is completed, but also tolerates and corrects up to a preselected number of skewed transitions to permit continuous pipeline operation, and detects up to a preselected greater number of skewed transitions (and invokes an error detection protocol) when the first preselected number of skewed transitions is exceeded.